This invention relates to the design of circuits with complex interconnections between circuit elements, and more particularly to methods for allocating interconnected circuit elements between two or more circuit element groups so that the number of interconnections required between the groups is minimized or at least substantially reduced.
In the design of large circuits, such as very large scale integrated ("VLSI") logic circuits, it is frequently necessary to subdivide the circuitry so that it can be implemented in two or more relatively discrete parts of one device or in two or more discrete devices. The circuit elements must be allocated between these two or more groups so that the number of interconnections required between the groups is not excessive. Indeed, it is usually desirable to find the allocation of circuit elements which reduces the number of required interconnections between the groups as much as possible. This problem, known as partitioning, has been extensively considered in the literature. See, for example, (1) B. W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs", The Bell System Technical Journal, February 1970, pp. 291-307 (see also U.S. Pat. No. 3,617,714); (2) D. G. Schweikert and B. W. Kernighan, "A Proper Model for the Partitioning of Electrical Circuits", Proceedings of the 9th Design Automation Workshop, 1979, pp. 57-62; (3) C. M. Fiduccia and R. M. Mattheyses, "A Linear-Time Heuristic for Improving Network Partitions", 19th Design Automation Conference, 1982, pp. 241-47; and (4) B. Krishnamurthy, "An Improved Min-Cut Algorithm for Partitioning VLSI Networks", IEEE Transactions on Computers, Vol. C-33, No. 5, May 1984, pp. 438-46, all of which are hereby incorporated by reference herein. Partitioning methods of the general type employed in the present invention are believed to have originated with reference (1) above, and to have progressed through additional enhancements in order with references (2), (3), and (4). The present invention comprises further modifications and improvements to the techniques shown and described in reference (4).
As noted above, the goal of a partitioning method is to partition or divide a set of circuit elements or "cells" connected by wires into two or more circuit element groups such that the number of wires which cross from one group to the other is minimized or at least substantially reduced. A circuit element group, as that term is employed herein, may be a discrete device such as an integrated circuit or a printed circuit board, or it may be a relatively discrete part of a larger device. For example, the two or more circuit element groups mentioned above may be two or more relatively discrete parts of a single integrated circuit such as a programmable logic array device. In the literature a set of cells connected by a common wire is generally referred to as a net. In at least the later references identified above (e.g., references (2)-(4)), a net can include any number of cells. Partitioning involves moving cells from one circuit element group to the other in an effort to reduce the number of connections required between the resulting circuit element groups. The prior art (and the present invention) provides methods for allowing various solutions to the partitioning problem to be tried in a systematic way in order to more rapidly and efficiently find the circuit element moves which give the best result.
In the above-mentioned prior art, it is generally assumed that dividing the cells of a net between two circuit element groups requires the use of two terminals or pins: one for the output from one circuit element group, and one for the input to the other circuit element group- Conversely, it is assumed that placing all the cells of net in one circuit element group allows the elimination of the two pins just described. This assumption is not always correct. For example, if a signal is an input to multiple cells which comes from outside the circuit (e.g., an external clock signal) or from a circuit element group other than the two groups currently being partitioned (where the circuit includes more than two circuit element groups), one pin is still required to apply the signal to the circuit element groups being partitioned even through all of the cells receiving that signal are in one of the circuit element groups being partitioned. When such cells are found in both circuit element groups being partitioned, two pins are required. Similarly, if a net signal is required as an output to the circuit or for application to a circuit element group other than the two currently being partitioned, one pin is again required to provide this output. When the cells of this net are split between the two circuit element groups being partitioned, two pins are required. In both of the examples mentioned above, the penalty for splitting the net is less than is assumed in the prior art such as reference (4), and conversely the benefit derived from not splitting the net is less than is assumed in the prior art such as reference (4). It would therefore be desirable to provide partitioning methods which more accurately take into account the effect of splitting nets which include connections external to the circuitry being partitioned.
The prior art such as reference (4) assumes that any cell is a candidate for movement from one circuit element group to another. However, the user of the method may know that certain cells should not be moved from the circuit group in which they have been placed initially (e.g., because those cells require some circuit resource which is unique to that circuit element group). It would therefore be desirable to provide partitioning methods which prevent certain cells from being moved.
The prior art such as reference (4) assumes that any net (or more generally, any collection or set of cells whether or not connected to one another in a net) can be split. The user of the method may know, however, that certain nets (or even unconnected sets of cells) should not be split (e.g., because splitting them would obviously result in inefficient use of some circuit resource). It would therefore be desirable to provide partitioning methods which prevent certain nets or sets of cells from being split.
The prior art such as reference (4) requires that a predetermined balance between the circuit element groups be preserved whenever a cell is moved from one group to the other. A cell is not allowed to move if the result will be that this balance requirement is violated. If the available circuit resources are at or close to full utilization, many possibly good moves may be precluded by this balance constraint, even though balance could be restored by subsequent moves. It would therefore be desirable to provide partitioning methods which do not require that balance between the circuit element groups be maintained with every move, but which ultimately do produce partitions which have the required balance.
In view of the foregoing, it is an object of this invention to provide improved circuit partitioning methods.
It is a more particular object of the invention to provide circuit partitioning methods which more accurately account for the effect of splitting or combining nets which utilize or are required to provide signals external to the circuit or the circuit element groups currently being partitioned.
It is another more particular object of the invention to provide circuit partitioning methods which allow the user to prevent certain cells from being moved and/or certain nets or sets of cells from being split.
It is still another more particular object of the invention to provide circuit partitioning methods which allow cells to be moved even though a specified balance between the circuit element groups is violated, said balance being restored by subsequent cell moves.